#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/12/19
# @Author   :Changshu
# @File     :Exercise_599.py
# 599. 两个列表的最小索引总和
# 假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
# 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设总是存在一个答案。

class Solution:
	def findRestaurant(self, list1: list, list2: list) -> list:
		d={}
		m=10**6
		res=[]
		for i in range(len(list1)):
			d[list1[i]]=i
		for j in range(len(list2)):
			s = list2[j]
			if s in d:
				d[s]=d[s]+j
				if d[s]<m:
					m=d[s]
					res=[s]
				elif d[s]==m:
					res.append(s)
		return res


if __name__ == '__main__':
	solution=Solution()
	list1=["Shogun", "Tapioca Express", "Burger King", "KFC"]
	list2=["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
	# list1=["Shogun","Tapioca Express","Burger King","KFC"]
	# list2=["KFC","Shogun","Burger King"]
	# list1=["Shogun","Tapioca Express","Burger King","KFC"]
	# list2=["KFC","Burger King","Tapioca Express","Shogun"]
	print(solution.findRestaurant(list1,list2))